与题目定义有些不同,表示人数,表示淘汰赛轮数。题目显然输入的是,根据它算出。为了方便2进制计算,编号从~。最后答案加1即可。同时,比赛胜败概率为了方便先除以100,用计算。
现在考虑如何计算答案,设为对的胜率,为第轮胜出的概率。那么有:
Chihik's Blog
与题目定义有些不同,n表示人数,m表示淘汰赛轮数。题目显然输入的是m,根据它算出n。为了方便2进制计算,编号从0~n−1。最后答案加1即可。同时,比赛胜败概率为了方便先除以100,用double计算。
现在考虑如何计算答案,设a[i][j]为i对j的胜率,f[i][j]为第i轮j胜出的概率。那么有:
貌似 @DDF_Van 大佬的标程过不了 , 有些题解用的二分会多一个logn,那就补一发倍增题解吧。
设dp[s][i][j]表示走了不多于s条边,i→j的最大边权(走不通为极小值)
前置知识:莫比乌斯反演,数论分块
这道题还是Trie树的板题,先将n个信息插入字典树中,对于查询的密码,在字典树中查询即可。
插入很好办,我们现在来讨论查询操作。我们记s1为任意一个信息,s2是待匹配的密码。tot[u]表示有多少个字符串经过点u,fin[u]表示有多少个字符串以点u结尾。
那么会出现三种情况:
我们应该用Tarjan缩点,将原图变为GAD图,同时记录每个强连通分量的节点个数,记为num[i]。
因为起点终点都是1,所以路径一定是一个环。我们可以处理出1到所有点的距离,存在dis1中(跑正图)和所有点到1的距离存在dis2中(跑反图)。注意,如果走不到就设为极小值。最短路跑的是点权,其实和边权差不多。
题目说可以逆向走一条有向边,我们设该边起点为u,终点为v,那么,答案就应为num[belong[1]]+max(dis1[v]+dis2[u])。